package main

import (
	"fmt"
	"sort"
)

// Section 1 -- Arrays
var (
	rotateMatrixTest = [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}

	isValidSudokuTest = [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	isValidSudokuTest2 = [][]byte{
		{'.', '1', '.', '5', '2', '.', '.', '.', '.'},
		{'.', '.', '.', '.', '.', '6', '4', '3', '.'},
		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
		{'5', '.', '.', '.', '.', '.', '9', '.', '.'},
		{'.', '.', '.', '.', '.', '.', '.', '5', '.'},
		{'.', '.', '.', '5', '.', '.', '.', '.', '.'},
		{'9', '.', '.', '.', '.', '3', '.', '.', '.'},
		{'.', '.', '6', '.', '.', '.', '.', '.', '.'},
		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
	}

	twoSumTest1 = []int{2, 7, 11, 15}
	twoSumTest2 = 9

	moveZeroesTest1 = []int{0, 1, 0, 3, 12}

	plusOneTest1 = []int{1, 2, 3, 7, 8, 9, 9}

	intersectTes1 = []int{1, 2, 2, 1}
	intersectTes2 = []int{1, 2, 2, 2}

	removeDuplicatesTest1  = []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 6}
	maxProfitTest1         = []int{7, 1, 5, 3, 6, 4}
	containsDuplicateTest1 = []int{1, 2, 3, 4}
	isAlienSortedOrder     = "zkgwaverfimqxbnctdplsjyohu"
	isAlienSortedwords     = []string{"fxasxpc", "d", "nwzgs", "cmwqriv", "ebulyfyve", "miracx", "sxckdwzv", "dtijzluhts", "wwbmnge", "qmjwymmyox"}
	singleNumberTest1      = []int{2, 2, 1}
)

func testArray() {
	printMatrix(rotateMatrixTest)
	rotateMatrix(rotateMatrixTest)
	printMatrix(rotateMatrixTest)
	return

	fmt.Println(isValidSudoku(isValidSudokuTest))

	fmt.Println(twoSum(twoSumTest1, twoSumTest2))

	moveZeroes(moveZeroesTest1)
	fmt.Println(moveZeroesTest1)

	fmt.Println(plusOne(plusOneTest1))

	fmt.Println(intersect(intersectTes1, intersectTes2))

	// test singleNumber
	fmt.Println(singleNumber(singleNumberTest1))

	// test containsDuplicate
	fmt.Println(containsDuplicate(containsDuplicateTest1))

	// test isAlienSorted
	fmt.Println(isAlienSorted(isAlienSortedwords, isAlienSortedOrder))

	// test rotate
	rotate(maxProfitTest1, 4)
	fmt.Println(maxProfitTest1)

	// test maxProfit
	fmt.Println(maxProfit(maxProfitTest1))

	// test removeDuplicates
	fmt.Println(removeDuplicates(removeDuplicatesTest1))
	fmt.Println(removeDuplicatesTest1)
}

func rotateMatrix(matrix [][]int) {
	l := len(matrix)
	// 对接线对称变换
	for i := 0; i < l; i++ {
		for j := i; j < l; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	// 左右对称变换
	for i := 0; i < l/2; i++ {
		for j := 0; j < l; j++ {
			matrix[j][i], matrix[j][l-i-1] = matrix[j][l-i-1], matrix[j][i]
		}
	}
}

func printMatrix(matrix [][]int) {
	for _, v1 := range matrix {
		fmt.Println(v1)
	}
	fmt.Println("--------")
}

func isValidSudoku(board [][]byte) bool {
	matrixSize := 9
	if len(board) != matrixSize {
		return false
	}

	// 行写0~8，列写9~17，宫写18~26
	var tmpMap [27][9]bool
	for i := 0; i < 27; i++ {
		for j := 0; j < 9; j++ {
			tmpMap[i][j] = false
		}
	}

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			newByte := board[i][j]
			if newByte == '.' {
				continue
			}

			num := newByte - '1'
			if tmpMap[i][num] || tmpMap[j+9][num] || tmpMap[i/3*3+j/3+18][num] {
				return false
			}

			tmpMap[i][num] = true
			tmpMap[j+9][num] = true
			tmpMap[i/3*3+j/3+18][num] = true
		}
	}
	return true
}

func twoSum(nums []int, target int) []int {
	hashMap := make(map[int]int)

	for index, num := range nums {
		newTarget := target - num
		if value, ok := hashMap[newTarget]; ok {
			return []int{value, index}
		}

		hashMap[num] = index
	}

	return nil
}

func moveZeroes(nums []int) {
	l := len(nums)
	count := 0
	for i := 0; i < l; i++ {
		if nums[i] == 0 {
			count++
			continue
		}

		if count > 0 {
			nums[i-count] = nums[i]
		}
	}

	for i := 0; i < count; i++ {
		nums[l-i-1] = 0
	}
}

func plusOne(digits []int) []int {
	l := len(digits)
	flag := 1
	for i := l; i > 0; i-- {
		flag = digits[i-1] + flag
		if flag < 10 {
			digits[i-1] = flag
			return digits
		} else {
			digits[i-1] = 0
			flag = 1
		}
	}

	ret := make([]int, l+1)
	ret[0] = 1
	return ret
}

func intersect(nums1 []int, nums2 []int) []int {
	ret := make([]int, 0)

	offset1 := 0
	offset2 := 0
	l1 := len(nums1)
	l2 := len(nums2)
	for offset1 < l1 && offset2 < l2 {
		for i := offset2; i < l2; i++ {
			if nums1[offset1] == nums2[i] {
				ret = append(ret, nums1[offset1])
				nums2[i] = nums2[offset2]
				offset2++
				break
			}
		}

		offset1++
	}

	return ret
}

func removeDuplicates(nums []int) int {
	bv, count := 0, -1
	for _, v := range nums {
		if count == -1 {
			bv = v
			count = 1
		}

		if v != bv {
			nums[count] = v
			bv = v
			count++
		}
	}

	return count
}

func maxProfit(prices []int) int {
	mp := 0
	if len(prices) < 2 {
		return mp
	}

	pre := prices[0]
	buy := prices[0]
	for _, v := range prices {
		if v < pre {
			mp += pre - buy
			buy = v
		}
		pre = v
	}

	if pre > buy {
		mp += pre - buy
	}

	return mp
}

/*
nums = []int{7, 1, 5, 3, 6, 4}
k = 4
rets = []int{5, 3, 6, 4, 7, 1}
*/
func rotate(nums []int, k int) {
	l := len(nums)
	if l < 2 {
		return
	}

	k = k % l
	if k == 0 {
		return
	}

	gcdCount := gcd(l, k)
	newI := 0
	newV := 0
	for i := 0; i < gcdCount; i++ {
		tmp := nums[i]
		for j := i; j < l || j%l != i; j += k {
			newI = (j + k) % l
			newV = nums[newI]
			nums[newI] = tmp
			tmp = newV
		}
	}
}

/*
*辗转相除法：最大公约数
*递归写法，进入运算是x和y都不为0
 */
func gcd(x, y int) int {
	tmp := x % y
	if tmp > 0 {
		return gcd(y, tmp)
	} else {
		return y
	}
}

func containsDuplicate(nums []int) bool {
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			return true
		}
	}

	return false
}

func singleNumber(nums []int) int {
	ret := 0
	for _, v := range nums {
		ret ^= v
	}
	return ret
}

func isAlienSorted(words []string, order string) bool {
	ol := len(order)
	wl := len(words)
	if ol != 26 {
		fmt.Println("ol != 26")
		return true
	}

	if wl < 2 {
		fmt.Println("wl < 2")
		return true
	}

	// order.length = 26
	orderMap := make(map[byte]int, ol)
	orderBytes := []byte(order)
	for i, v := range orderBytes {
		orderMap[v] = i
	}

	preWord := []byte(words[0])
	for k, v := range words {
		if k == 0 {
			continue
		}

		nowWord := []byte(v)
		breakOut := false
		for offset, key := range nowWord {
			if offset == len(preWord) {
				breakOut = true
				break
			}

			fmt.Printf("%d:%c-%d:%c-%d\n", offset, preWord[offset], orderMap[preWord[offset]], key, orderMap[key])
			if orderMap[key] > orderMap[preWord[offset]] {
				breakOut = true
				break
			} else if orderMap[key] < orderMap[preWord[offset]] {
				return false
			} else if orderMap[key] == orderMap[preWord[offset]] {
				continue
			}
		}

		if len(nowWord) < len(preWord) && !breakOut {
			return false
		}

		preWord = nowWord
	}

	return true
}
